The present invention relates to an apparatus for performing secret communications and digital signatures by a public key cryptosystem, and especially relates to a message recovery signature apparatus whose security is based on the discrete logarithm problem.
Nyberg-Rueppel proposes a message recovery signature scheme which is carried out by a public key cryptosystem using the discrete logarithm problem as a basis for security (see Nyberg and Rueppel xe2x80x9cA New Signature Scheme Based on the DSA Giving Message Recoveryxe2x80x9d 1st ACM Conference on Computer and Communications Security (1993)).
xe2x80x9cDiscrete logarithmxe2x80x9d is a logarithm over a finite field.
xe2x80x9cDiscrete logarithm problemxe2x80x9d is as follows. Let p be a prime number or a prime number raised to a given power, g be a primitive root of a finite field GF(p), and y, p, and g be any elements of GF(p) aside from zero. The problem is to find an integer x that satisfies
y=gxxe2x80x83xe2x80x83(Equation 1.1)
where 0xe2x89xa6xxe2x89xa6pxe2x88x921.
xe2x80x9cUsing the discrete logarithm problem as a basis for securityxe2x80x9d is due to the following reason. Though the exponential calculation is easy, the above logarithmic calculation is extremely difficult for a large finite field GF(p), such as GF(2127) Such a logarithmic calculation corresponds to the calculation of the inverse of a one-way function and thus assists in the security of encryption.
xe2x80x9cPublic key cryptosystemxe2x80x9d is a cryptosystem that uses different keys for encryption and decryption, with the decryption key being kept secret and the encryption key being made public. Public key encryption provides a convenient method for managing the separate encryption keys of many users, and so has become a fundamental technique for performing communications with a large number of users.
xe2x80x9cMessage recovery signaturexe2x80x9d is a signature for certifying the validity of the signer, with the message being embedded within the signature. With this technique, the message and the signature do not have to be sent separately, so that the traffic for transmission can be reduced.
FIG. 11 is a sequential view showing the processing of the above conventional signature scheme.
A user A 610, a management center 620, and a user B 630 are connected with each other via a network. Here, the user A 610 signs a message m and sends it to the user B 630 under management of the management center 620.
 less than Public Key Generation greater than 
A prime number is set as p, an element of GF(p) is set as g, and the order of g is set as q as the system conditions. Which is to say, q is the smallest integer that satisfies
gq=1(mod p)xe2x80x83xe2x80x83(Equation 1.2)
First, the management center 620 generates a public key yA for the user A 610 using the user A""s secret key xA which has been informed beforehand, according to
yA=gxAxe2x80x83xe2x80x83(Equation 1.3)
(S640xcx9cS641).
The management center 620 then reveals the system parameters p, q, and g together with the public key yA of the user A 610 to the user B 630 (S643)
 less than Signature and Transmission greater than 
The user A 610 generates a random number k (S644), calculates
r1=gk(mod p)xe2x80x83xe2x80x83(Equation 1.4)
xe2x80x83r2=m/r1(mod p)xe2x80x83xe2x80x83(Equation 1.5)
r2xe2x80x2=r2(mod q)xe2x80x83xe2x80x83(Equation 1.6)
s=kxe2x88x92r2xe2x80x2xA(mod q)xe2x80x83xe2x80x83(Equation 1.7)
in sequence (S645xcx9cS648), and sends s and r2 to the user B 630 as a ciphertext (r2,s) (S649).
Here, r1 is referred to as a commitment, Equation 1.5 as a message-mask equation, and Equation 1.7 as a signature equation. Equation 1.7 leads to the following six types of
ak=b+cxA(mod q)xe2x80x83xe2x80x83(Equation 1.8)
where (a,b,c) is a permutation of (1,r2xe2x80x2,s), that is,
a=1, b=r2xe2x80x2, c=s
a=1, b=s, c=r2xe2x80x2
a=r2xe2x80x2, b=1, c=s
a=r2xe2x80x2, b=s, c=1
a=s, b=r2xe2x80x2, c=1
a=s, b=1, c=r2xe2x80x2
Note that (mod p) and (mod q) denote operations modulo p and q, respectively.
 less than Message Recovery greater than 
The user B 630 receives the ciphertext (r2,s) and recovers the message m by computing
gsyAr2xe2x80x2r2=m(mod p)xe2x80x83xe2x80x83(Equation 1.9)
with the revealed public key yA and system parameters p, q, g, a, b, and c (S650). Equation 1.9 is derived from   "AutoLeftMatch"                                                                        m                =                                                      r                    1                                    ⁢                                      r                    2                                                                                                                          =                                                      g                    k                                    ⁢                                      r                    2                                                                                                                          =                                                      g                                          s                      +                                                                        r2                          xe2x80x2                                                ⁢                        xA                                                                              ⁢                                      r                    2                                                                                                                          =                                                      g                    s                                    ⁢                                      g                                          xAr2                      xe2x80x2                                                        ⁢                                      r                    2                                                                                                                          =                                                      g                    s                                    ⁢                                      y                    A                                          r2                      xe2x80x2                                                        ⁢                                      r                    2                                                                                                            (Equation  1.10)                    
Thus, the above conventional scheme is a breakthrough in the sense that message recovery signatures by a public key cryptosystem based on the discrete logarithm problem are made possible for the first time.
Nevertheless, this conventional scheme is vulnerable to four types of attack given below.
(Signature-equation Attack)
The signature-equation attack is as follows.
If a forger acquires the message m and its signature (r2,s), the forger can forge a new message mgd (d is any element of GF(p)), sign the message mgd, and send it to the user B.
Which is to say, the forger sends a ciphertext (r2,s+d) to the user B. The user B then calculates   "AutoLeftMatch"                                                                                                              g                                          s                      +                      d                                                        ⁢                                      y                    A                                          r2                      xe2x80x2                                                        ⁢                                      r                    2                                                  =                                                      g                    s                                    ⁢                                      y                    A                                          r2                      xe2x80x2                                                        ⁢                                      r                    2                                    ⁢                                      g                    d                                                                                                                          =                                  m                  ⁢                                      xe2x80x83                                    ⁢                                      g                    d                                                                                                            (Equation  1.11)                    
If the recovered message mgd is intelligible, the user B will think that the message is from the user A. Hence the forger can successfully sign the new message mgd without knowledge of the secret key xA.
(Homomorphism Attack)
The homomorphism attack is as follows.
If a forger chooses a message mm, has the user A sign the message mm, and acquires the signature, the forger can impersonate the user A and sign a desired message mmgd.
This attack is possible for the same reason as the signature-equation attack. The difference with the signature-equation attack is that the forger can sign the desired message mmgd.
(Redundancy Attack)
The redundancy attack is as follows.
If a forger acquires the message m and its signature (r2,s), the forger can sign a new message mm that satisfies
rr2=r2xe2x80x2+nq(xe2x89xa0r2)xe2x80x83xe2x80x83(Equation 1.12)
mm=rr2xc3x97(m/r2)xe2x80x83xe2x80x83(Equation 1.13)
Which is to say, the forger sends a ciphertext (rr2,s) to the user B. Then the user B computes                     "AutoLeftMatch"                                                                                                  g                    s                                    ⁢                                      y                    A                                          rr2                      xe2x80x2                                                        ⁢                                      rr                    2                                                  =                                                      g                    s                                    ⁢                                      y                    A                                          r2                      xe2x80x2                                                        ⁢                                      rr                    2                                                                                                                          =                                                      (                                          m                      /                                              r                        2                                                              )                                    ⁢                                      rr                    2                                                                                                                          =                                  m                  ⁢                                      xe2x80x83                                    ⁢                  m                                                                                        (Equation  1.14)            
If the recovered message mm is intelligible, the user A will think that the message is from the user A.
This attack is based on redundancy between r2xe2x80x2 used in Equation 1.7 and r2 calculated in Equation 1.6.
(Recovery-equation Attack)
The recovery-equation attack is as follows.
Without performing communications beforehand, a forger can sign a message MyAe (e is an element of GF(p)) using any new M (M is an element of GF(p)).
Specifically, the forger determines rr2 and ss that satisfy
rr2=Myugv (where u and v are elements of GF(p))xe2x80x83xe2x80x83(Equation 1.15)
ss=xe2x88x92vxe2x80x83xe2x80x83(Equation 1.16)
e=rr2xe2x80x2+uxe2x80x83xe2x80x83(Equation 1.17)
and sends a ciphertext (rr2,ss) to the user B. The user B then calculates   "AutoLeftMatch"                                                                                                              g                    ss                                    ⁢                                      y                    A                                          rr2                      xe2x80x2                                                        ⁢                                      rr                    2                                                  =                                                      y                    A                    e                                    ⁢                  My                                                                                                        =                                  My                  A                  e                                                                                          (Equation  1.18)                    
If the recovered message MyAe makes sense, the user B will think that the message is from the user A.
This attack is based on that, for the elements u and v of GF(p), there are solutions that satisfy
rr2=MyAugvxe2x80x83xe2x80x83(Equation 1.19)
v=xe2x88x92b/a (where a and b are elements of {1,r2xe2x80x2,s})xe2x80x83xe2x80x83(Equation 1.20)
The above four attacks are detailed in Atsuko Miyaji Weakness in Message Recovery Signature Schemes 1 Institute of Electronics, Information, and Communication Engineers, Information Security Workshop (July 1995), Nyberg and Rueppel xe2x80x9cA New Signature Scheme Based on the DSA Giving Message Recoveryxe2x80x9d 1st ACM Conference on Computer and Communications Security (1993), and Nyberg and Rueppel xe2x80x9cMessage Recovery for Signature Schemes Based on the Discrete Logarithm Problemxe2x80x9d Advances in Cryptology-Proceedings of Eurocrypt ""94, Lecture Notes in Computer Science, vol.950 (1995) Springer-Verlag, pp.182xcx9c193.
Thus, the conventional message recovery signature scheme is weak against the four attacks that can forge signatures of messages which satisfy certain conditions.
In view of the stated problems of the conventional signature scheme, the present invention aims to provide a message recovery signature apparatus that is secure against the above four attacks.
The above object can be fulfilled by a message recovery signature apparatus for signing a message m with a secret key xA using a discrete logarithm problem as a basis for security, based on operations performed on a finite field GF(p) where p is a prime number and g is an element whose order is q, the message recovery signature apparatus including: a random number generating unit for generating a random number k; a commitment generating unit for generating a commitment r1 from the random number k according to a function f11(k)=gk; a message masking unit for generating a masked message r2 from the commitment r1 and the message m according to a function f12(r1,m) that maps GF(p)xc3x97GF(p) into the finite field GF(p); and a signature generating unit for generating a signature s from the masked message r2 and the secret key xA according to a function f13(r2,xA) the message recovery signature apparatus being characterized in that the function f12(r1,m) has a property that when gxA denotes a public key yA and t, j, and e denote elements of a finite ring Zq={0, 1, . . . , qxe2x88x921}, the three variables t, j, and e are unable to be replaced with two algebraic relations in f12(gtyAj,myAe) and f12(gtyAj,mge).
With this construction, substituting Mge or MyAe for the message m cannot determine the three variables t, j, and e that satisfy r2=f12( ). Also, the inverse fxe2x88x921 of the map f is
fxe2x88x921(r1/g,r2)xe2x89xa0xcfx86(m,g)
and
fxe2x88x921(r1/yA,r2)xe2x89xa0xcfx86(m,yA)
respectively for arbitrary functions xcfx86 and xcfx86 of two variables. Accordingly, the recovery-equation attack and the homomorphism attack can be avoided.
Here, the signature generating unit may calculate, when Zq={0, 1, . . . , qxe2x88x921} is a finite ring and ha, hb, and hc are functions that map Zqxc3x97Zqxc3x97Zq into Zq, a signature s which satisfies
ha(r2xe2x80x2,s,1)k=hb(r2xe2x80x2ks,1)+hc(r2xe2x80x2,s,1)xA(mod q)
where the functions ha, hb, and hc satisfy conditions (1) and (2):
(1) if ha(r2xe2x80x2,s,1)=ha(rr2xe2x80x2,ss,1) and hc(r2xe2x80x2,ss,1)=hc(rr2xe2x80x2,ss,1), then hb(r2xe2x80x2,s,1)xe2x88x92ha(r2xe2x80x2,s,1)xe2x89xa0hb(rr2xe2x80x2,ss,1)
(2) if ha(r2xe2x80x2,s,1)=ha(rr2xe2x80x2,ss,1) and hb(r2xe2x80x2,s,1)=hb(rr2xe2x80x2,ss,1), then hc(r2xe2x80x2,s,1)xe2x88x92ha(r2xe2x80x2,s,1)xe2x89xa0hc(rr2,ss,1)
for any elements rr2xe2x80x2 and ss of the finite ring Zq aside from a few prefixed values.
With this construction, a forger who tries to sign a message mgd cannot find rr2xe2x80x2 and ss which satisfy the signature equation (that is, rr2xe2x80x2=ss=0). Accordingly, the signature-equation attack can be avoided.
Here, the message recovery signature apparatus may further include: a judging unit for judging whether the masked message r2 generated by the message masking unit meets a condition 0 less than r2 less than q; and a repeating unit for having, when the judging unit judges that the condition is unmet, the random number generating unit, the commitment generating unit, and the message masking unit respectively generate a new random number k, a commitment r1, and a masked message r2.
With this construction, the redundancy between r2 and r2xe2x80x2 is eliminated. Accordingly, the redundancy attack can be avoided.
Here, the operations may be performed on a finite field GF(pr) instead of a finite field GF(p).
Here, the operations may be performed on an elliptic curve E(GF(p)) or E(GF(pr)) instead of a finite field GF(p). With this construction, faster message recovery signature processing and recovery processing, strengthened security, and compact circuitry and software implementations can be achieved.